package utils.perfectHash;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

import com.google.common.base.Equivalence;

public class EasyPerfectMinimalHashing<E> extends Equivalence<E> {

	private final int[] g;
	
	EasyPerfectMinimalHashing(int[] g) {
		this.g=g;
	}
	
	@Override
	protected boolean doEquivalent(E arg0, E arg1) {
		return arg0.equals(arg1);
	}

	@Override
	protected int doHash(E arg0){
		int hash=hash(0,arg0, g.length);
		int d=g[hash];
		if(d<0){
			return -d-1;
		}
		hash=hash(d,arg0, g.length);
		
		return hash;
	}
	
	public int size(){
		return g.length;
	}
	
	private static int hash(int d, Object arg0,int size){
		if(d==0){
			d=0x01000193;
		}
		for(byte c : getObjectAsBytes(arg0)){
			d= ((d*0x01000193)^c ) & 0xffffffff;
		}
		d=d%size;
		if(d<0){
			return d+size;
		}
		return d;
	}
	
	private static byte[] getObjectAsBytes(final Object arg0){
		final ByteArrayOutputStream bos= new ByteArrayOutputStream();
		ObjectOutputStream oos=null;
		try{
			oos=new ObjectOutputStream(bos);
			oos.writeObject(arg0);
			oos.flush();
			oos.close();
			bos.close();
			return bos.toByteArray();
		}catch (IOException e){
			//ignore
		}
		return new byte[0];
	}
	
	public static <E> EasyPerfectMinimalHashing<E> createEasyPerfectMinimalHashing(Collection<? extends E> keys){
		int size=keys.size(), hash, slot;
		int[] g= new int[size];
		BitSet used= new BitSet(size);
		
		System.err.println("create buckets ...");
		ArrayList<E> buckets[]= new ArrayList[size];
//		ArrayList<ArrayList<E>> buckets= new ArrayList<ArrayList<E>>(size);
		ArrayList<E> bucket;
		ArrayList<Integer> slots;
		for(int i=0;i<size;++i){
			buckets[i]= new ArrayList<E>();
		}
		System.err.println("fill buckets ...");
		for(E key : keys){
			buckets[hash(0,key, size)].add(key);
		}
		System.err.println("Sort buckets ...");
		Arrays.sort(buckets, new ArrayListLengthCompareable());
//		Collections.sort(buckets, new ArrayListLengthCompareable());

		System.err.println("Start the bucket processing...");
		int b=0;
		for(;b<size;++b){
			bucket=buckets[b];
			if(bucket.size()<=1){
				break;
			}
			int d=1,
					item=0;
			slots= new ArrayList<Integer>();
			while(item < bucket.size()){
				slot= hash(d, bucket.get(item), size);
				if(used.get(slot) || slots.contains(slot)){
					++d;
					item=0;
					slots= new ArrayList<Integer>();
				}else{
					slots.add(slot);
					++item;
				}
			}
			g[hash(0,bucket.get(0),size)]=d;
			for(Integer set: slots){
				used.set(set);
			}
			if(b % 1000 ==0){
				System.err.print("buckets completed: "+b+"\r");
			}
		}
		slot=-1;
		for(;b<size;++b){
			bucket= buckets[b];
			if(bucket.size()==0){
				break;
			}
			slot=used.nextClearBit(slot+1);
			g[hash(0,bucket.get(0),size)]= -slot-1;
			
			if(b%1000==0){
				System.err.print("buckets completed: "+b+"\r");
			}
		}
		System.err.println("buckets completed: "+b);

		return new EasyPerfectMinimalHashing<E>(g);
	}

	
}

class ArrayListLengthCompareable implements Comparator<ArrayList>{

	@Override
	public int compare(ArrayList o1, ArrayList o2) {
		// TODO Auto-generated method stub
		return o2.size()-o1.size();
	}
	
}
